package com.yulongtian.oneProblemEveryDay.month202302;

/**
 * https://leetcode.cn/problems/replace-the-substring-for-balanced-string/
 * 可
 *
 * @author yulongTian
 * @create 2023-02-13 8:07
 */
public class Test10 {
    public static void main(String[] args) {
        System.out.println(balancedString("WWEQERQWQWWRWWERQWEQ"));
    }

    /**
     * 使用两个指针算法来确保两个指针之外的所有字符数量都小于或等于 n/4。
     * 这意味着你需要计算每个字母的数量，并确保数量是足够的。
     * WWEQERQWQWWRWWERQWEQ
     * 替换一个子串   需要连续
     * <p>
     * 一个很容易理解的思路：
     * 记录Q、W、E、R这四个字母中各自超出n/4的多余频率数（未超出则计为0。比如“QQQW”就是[2, 0, 0, 0]），
     * 然后在s中找最短的、包围这些频率数的子串长度（滑动窗口），这个长度就是答案。
     * 必要性：多出来的那些频率总要被抹平的；
     * 充分性：拿了这些字符后，QWER的频数都不会超过n/4，接下来缺哪补哪就平衡了。
     *
     * @param s
     * @return
     */
    public static int balancedString(String s) {
        char[] chs = s.toCharArray();
        char[] tar = {'Q', 'W', 'E', 'R'};
        int n = s.length();
        int[] cnt = new int[4];

        for (char c : chs) {
            if (c == 'Q') {
                cnt[0]++;
            } else if (c == 'W') {
                cnt[1]++;
            } else if (c == 'E') {
                cnt[2]++;
            } else {
                cnt[3]++;
            }
        }

        int targetNum = 0;
        String targetS = "";
        for (int i = 0; i < cnt.length; i++) {
            cnt[i] = Math.max(cnt[i] - n / 4, 0);
            targetNum += cnt[i];
            if (cnt[i] > 0) {
                targetS += tar[i];
            }
        }
        //目标字符数组 Q W
        char[] tarChs = targetS.toCharArray();
        int[] tar_cnt = new int[tarChs.length];
        int[] pre_cnt = new int[tarChs.length];
        int index = 0;
        for (int i : cnt) {
            if (i > 0) {
                pre_cnt[index] = i;
                index++;
            }
        }

        if (targetNum == 0) {
            return 0;
        }

        //双指针
        int left = 0;
        int ans = n + 1;
        int c_cnt = 0;
        for (int right = 0; right < n; right++) {
            for (int i = 0; i < tarChs.length; i++) {
                if (tarChs[i] == chs[right]) {
                    tar_cnt[i]++;
                    break;
                }
            }

            //当频数满足时
            while (check(pre_cnt, tar_cnt)) {
                ans = Math.min(ans, right - left + 1);
                for (int i = 0; i < tarChs.length; i++) {
                    if (tarChs[i] == chs[left]) {
                        tar_cnt[i]--;
                        break;
                    }
                }
                left++;
            }
        }
        return ans;
    }

    //判断是否都满足  均大于等于频数
    public static boolean check(int[] cnt, int[] tar_cnt) {
        for (int i = 0; i < cnt.length; i++) {
            if (tar_cnt[i] < cnt[i]) {
                return false;
            }
        }
        return true;
    }


}
